package com.sun.test;

/**
 * 二分法查找数组
 */
public class binarySearchArray {
    public static void main(String[] args) {
        /*5.二分法查找操作：使用二分法查找有序数组中元素。找到返回索引，不存在输出-1。
        分析：二分法查找的前提是数组有序。
        假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.　　
        1)开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。
        2)令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。
        3)令新的front=mid+1=2，而end=2不变，则新mid=2，此时a[mid]=x，查找成功。
        4)如要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。*/
        //1.声明一个一维数组
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        //System.out.println(searchLoop(array, 9));

        /*6.二维数组遍历求和操作：用二重循环求出二维数组b所有元素的和：
        int[][] b={{11},{21,22},{31,32,33}}*/

        int[][] b={{11},{21,22},{31,32,33}};
        int sum=0;
       for (int i = 0; i < b.length; i++){
           for (int j = 0; j < b[i].length; j++) {
                sum+=b[i][j];
           }
       }
        System.out.println(sum);
    }

    /**
     * 循环二分法查找，返回第一次出现该值的位置
     * @param arr 已排序的数组
     * @param findValue 需要查找的值
     * @return 值在数组中的位置，直接返回-1，即查找失败
     */
    public static  int searchLoop(int[] arr,int findValue){
        //如果数组为空，直接返回-1，即查找失败
        if(arr==null){
            return -1;
        }
        //起始位置
        int start=0;
        //结束位置
        int end=arr.length-1;
        while (start<=end){
            //中间位置
            int middle=(start+end)/2;
            //中值
            int middleValue=arr[middle];
            if(findValue==middleValue){
                //等于中间值直接返回
                return middle;
            }else if(findValue<middleValue){
                //小于中值时在中值前面查找
                end=middle-1;
            }else {
                //大于中值在中值后面查找
                start=middle+1;
            }
        }
        //返回-1，即查找失败
        return -1;
    }
}
